package leetcode.weekly.week325;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

//Solution4Test
public class Solution4 {

	int mod = (int) 1e9 + 7;

	public int countPartitions(int[] nums, int k) {
		Arrays.sort(nums);
		long sum = 0;
		for (int num : nums) {
			sum += 1l * num;
		}
		Map<Long, Long> cnts = new HashMap<>();
		cnts.put(0l, 1l);
		for (int num : nums) {
			Map<Long, Long> adds = new HashMap<>();
			adds.put(1l * num, 1l);
			for (Map.Entry<Long, Long> entry : cnts.entrySet()) {
				long key = entry.getKey(), value = entry.getValue();
				long add = key + num;
				adds.put(add, value);
			}
			for (Map.Entry<Long, Long> entry : adds.entrySet()) {
				cnts.put(entry.getKey(), (cnts.getOrDefault(entry.getKey(), 0l) + entry.getValue()) % mod);
			}
		}
		long ans = 0;
		for (Map.Entry<Long, Long> entry : cnts.entrySet()) {
			long key = entry.getKey(), value = entry.getValue();
			if (key >= k && sum - key >= k) {
				ans += value;
				ans %= mod;
			}
		}
		return (int) ans;
	}

}
